#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <list>
#include <deque>
#include <algorithm>
using namespace std;

#define __map map // map type used

template<class K, class V>
struct mymap
{
	typedef long long timestamp;
	typedef typename __map<K, V> map_type;
	typedef typename __map<K, timestamp> K2T;
	typedef typename __map<timestamp, K> T2K;

	map_type data;
	K2T k2t;
	T2K t2k;

	// fields
	timestamp tm;
	size_t capacity;
	mymap(size_t cap=10) { tm=1; capacity=cap;}

	V& operator[](const K& k)
	{
		timestamp& _tm=k2t[k];
		if(_tm)
			t2k.erase(_tm);
		_tm=tm++;
		t2k[_tm]=k;

		V& ret=data[k];

		if(size() && shouldRemoveEldest())
			erase(t2k.begin()->second);

		return ret;
	}
	size_t size(){ return data.size(); }
	void erase(const K k)
	{
		t2k.erase(k2t[k]);
		k2t.erase(k);
		data.erase(k);
	}

	bool shouldRemoveEldest()
	{
		return size()>capacity;
	}
};

typedef mymap<string, int> cache_map;

typedef pair<string, int> PSI;
int main()
{
	cache_map mm1(1000);

	char s[4]="123";
	for(int rpt=10000; rpt>0;rpt--)
	{
		s[0]=char(rand()%('z'-'a')+'a');
		s[1]=char(rand()%('z'-'a')+'a');
		s[2]=char(rand()%('z'-'a')+'a');

		if(rand()%2==0)
		{
			s[0]='a';
			if(rand()%2==0)
			{
				s[1]='a';
				if(rand()%2==0)
					s[2]='a';
			}
		}

		mm1[s]++;
	}

	return 0;
}